home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
vol_300
/
347_01
/
tavltree.doc
< prev
next >
Wrap
Text File
|
1991-10-17
|
17KB
|
413 lines
/*:file:version:date: "%n V.%v; %f"
* "TAVLTREE.DOC V.3; 18-Feb-91,15:23:10"
*
* Purpose: Documentation for TAVL library.
*
* Copyright (c) 1991 Bert C. Hughes
* 200 N.Saratoga
* St.Paul, MN 55104
* Compuserve 71211,577
*/
------------------------------------------------
TAVL library public functions, types & constants
------------------------------------------------
---------
CONSTANTS
---------
- Can be used as parameters for function tavl_insert -
REPLACE ........ 1
NO_REPLACE ..... 0
- Return values of function tavl_setdata -
TAVL_OK ........ 0 No error.
TAVL_NOMEM ..... 1 Out of memory error.
TAVL_ILLEGAL_OP 2 Requested operation would disrupt the
tavl_tree structure; operation cancelled.
-----
TYPES
-----
TAVL_treeptr Pointer to a TAVL tree. Most tavl library
functions require a TAVL_tree pointer as the
first parameter. A valid TAVL_treeptr can
only be obtained via the function "tavl_init",
which returns a TAVL_treeptr which can then be
used as a parameter for other TAVL functions.
All fields in *TAVL_treeptr are absolutely,
unequivocally PRIVATE. No point in even
reading them.
TAVL_nodeptr Pointer to a TAVL tree node. Many TAVL functions
require a TAVL_nodeptr as parameter, or return a
TAVL_nodeptr. Fields within *TAVL_nodeptr are
PRIVATE - with one possible, but unnecessary,
exception: TAVL_nodeptr->dataptr - in which case
it is READONLY.
Data should be obtained from a TAVL_nodeptr
via the function "tavl_getdata", rather than
reading "dataptr" directly.
-----------------
FUNCTIONS
-----------------
TAVL_INIT
---------
purpose: Creates a new TAVL tree. Returned pointer is used
as a parameter to TAVL routines in subsequent
processing.
source file: tavlinit.c
returns: pointer to empty tree, or NULL if
insufficient memory.
prototype: TAVL_treeptr tavl_init(
int (*compare)(void *Key1, void *Key2),
void *(*key_of)(void *DataObject),
void *(*make_item)(const void *DataObject),
void (*free_item)(void *DataObject),
void *(*copy_item)(void *Dest_DataObject,
const void *Source_DataObject),
void *(*alloc)(size_t),
void (*dealloc)(void *)
);
parameters: All parameters for tavl_init are pointers to functions,
so that you can tailor the behavior of the tavltree and
the data it stores to fit the needs of your application.
compare - Exclusively defines how the tavl library will
make comparisons for this tree.
must return:
0 - (Key1 == Key2)
>0 - (Key1 > Key2)
<0 - (Key1 < Key2)
key_of - Must return a pointer to the identifier of
data objects which are being inserted into
this instance of tavl tree. Within the TAVL
library, result of the "key_of" function is
passed directly to the "compare" function.
(Identifier - that which distinguishes this
data object from other data objects.
Its "name".)
make_item - Must create a copy of the data object passed
to it. This function is also responsible for
allocating memory necessary for storing the
copy of the data object. Library function
tavl_insert uses "make_item" to make a copy
of the item, or object, to insert into the
tree, and library function tavl_setdata uses
"make_item" to create a copy of the data
item passed to it.
free_item - Opposite of make_item. Function "free_item"
must free or deallocate memory given to
the object by "make_item".
copy_item - Copies a data object to a buffer. All memory
necessary to store the object must have been
allocated before "copy_item" is called.
alloc - A memory allocator for the tavl library to
use for its private purposes, ie, allocation
of nodes and struct tavltree.
dealloc - Counterpart to "alloc".
Often "alloc" & "dealloc" will be the complementary
C library functions "malloc" and "free".
TAVL_INSERT
-----------
purpose: Inserts data objects into the tree.
source file: tavl_ins.c
returns: A pointer to the node which contains the data object
inserted or found.
prototype: TAVL_nodeptr tavl_insert(
TAVL_treeptr tree,
void *item,
int replace
);
parameters: tree - Pointer to the tree into which data will be
inserted.
item - Pointer to the object to insert.
replace - Instructs "tavl_insert" on how to behave
if the tree already contains a data object
whose identifier equals key_of(item).
If replace != 0, the new data object will
replace the old, otherwise nothing happens,
tavl_insert simply returns a pointer to
the found node.
NOTES: "tavl_insert" requires the private function
"rebalance_tavl" contained in source file "tavlrebl.c",
so the module "tavlrebl.obj" (or whatever, depending on
your system) must be linked to the final executable
program.
TAVL_DELETE
-----------
purpose: Deletes node containing item such that
*key_of(node.item) == *key.
source file: tavl_del.c
returns: 1 if successful, otherwise 0.
prototype: int tavl_delete(TAVL_treeptr tree, void *key);
parameters: tree - Tree to remove object from.
key - Identifier of object to remove.
NOTES: "tavl_delete" requires the private function
"rebalance_tavl" contained in source file "tavlrebl.c",
so the module "tavlrebl.obj" (or whatever, depending on
your system) must be linked to the final executable
program.
TAVL_FIND
---------
purpose: Find node whose data object's identifier
equals *key.
source file: tavlfind.c
prototype: TAVL_nodeptr tavl_